package Algorithm.dfs;

import java.util.ArrayList;
import java.util.List;

//https://leetcode-cn.com/problems/coloring-a-border/
//1034. 边界着色
public class Leetcode1034_coloring_a_border {
    class Solution {
        private boolean[][] vis;
        private List<Integer> list;
        private int[] vx = {1,-1,0,0};
        private int[] vy = {0,0,1,-1};

        public int[][] colorBorder(int[][] grid, int row, int col, int color) {
            vis = new boolean[grid.length][grid[0].length];
            int target = grid[row][col];
            this.list = new ArrayList();

            dfs(grid, row, col, color, target);

            for(int i=0;i<list.size();i++){
                int coord = list.get(i);
                int x = coord/grid[0].length;
                int y = coord%grid[0].length;

                grid[x][y] = color;
            }


            return grid;
        }

        public void dfs(int[][] grid, int row, int col, int color,int target){
            if(row<0||row>=grid.length||col<0||col>=grid[0].length||vis[row][col])
                return;

            vis[row][col] = true;
            boolean flag = false;
            if(row==0||row==grid.length-1||col==0||col==grid[0].length-1){
                flag = true;
            }
            for(int i=0;i<4;i++){
                int x = row + vy[i];
                int y = col + vx[i];
                if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&!vis[x][y]){
                    if(!flag&&grid[x][y]!=target){
                        flag = true;
                    }

                    if(grid[x][y]==target){
                        dfs(grid,x,y,color,target);
                    }
                }
            }

            if(flag){
                this.list.add(row*grid[0].length + col);
            }

        }


    }
}
